// 快速排序使用分治法把一个数列（list）分为2个数列（sub-lists），具体算法以下：shell

// 从数列中挑出一个元素，称为 “基准”（pivot）；
// 从新排序数列，全部元素比基准值小的摆放在基准前面，全部元素比基准值大的摆在基准的后面（相同的数能够到任一边）。在这个分区退出以后，该基准就处于数列的中间位置。这个称为分区（partition）操做；
// 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

function quickSort(arr, left, right) {
  var len = arr.length,
      partitionIndex,
      left = typeof left != 'number'? 0 : left,
      right = typeof right != 'number'? len -1 : right;
  if(left < right) {
      partitionIndex = partition(arr, left, right);
      quickSort(arr, left, partitionIndex-1);
      quickSort(arr, partitionIndex+1, right);
  }
}
// 分区操做
function partition(arr, left, right) { 
  // 设定基准值pivot
  var pivot = left,
      index = pivot+1;
  for(var i = index;i<= right;i++){
      if(arr[i] < arr[pivot]){
          swap(arr, i, index);
          index++;
      }
  }
  swap(arr, pivot, index-1);
  return index-1;
}
// 交换数据
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
